package com.zhanghp.class036;

import com.zhanghp.common.TreeNode;

import java.util.*;

/**
 * 二叉树的层序遍历<br/>
 * 测试链接 : https://leetcode.cn/problems/binary-tree-level-order-traversal/
 *
 * @author zhanghp
 * @since 2024/4/15 13:51
 */
public class Code01_LevelOrderTraversal {

    static class Solution {

        // 每一层所有节点从左到右，依次放入队列
        // 然后遍历queue的size，对该层级的val收集，然后把每个节点的左，右孩子再次放入queue
        public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> ans = new ArrayList<>();
            if (root == null) {
                return ans;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) {
                List<Integer> nodeVals = new ArrayList<>();
                int size = queue.size();
                // 遍历层级节点
                for (int i = 0; i < size; i++) {
                    TreeNode node = queue.poll();
                    nodeVals.add(node.val);
                    if (node.left != null) {
                        queue.add(node.left);
                    }
                    if (node.right != null) {
                        queue.add(node.right);
                    }
                }
                ans.add(nodeVals);
            }
            return ans;
        }
    }

    static class Solution2{
        public int MAX_SIZE = 2001;

        public TreeNode[] queue = new TreeNode[MAX_SIZE];

        public int l, r;

        // 提交时把方法名改为levelOrder，此方法为每次处理一层的优化bfs，此题推荐
        public List<List<Integer>> levelOrder2(TreeNode root){
            List<List<Integer>> ans = new ArrayList<>();
            if (root == null) {
                return ans;
            }
            l = r= 0;
            queue[r ++] = root;
            while (l < r){
                ArrayList<Integer> list = new ArrayList<>();
                int size = r - l;
                for (int i = 0; i < size; i++) {
                    TreeNode a = queue[l++];
                    list.add(a.val);
                    if (a.left != null) {
                        queue[r ++] = a.left;
                    }
                    if (a.right != null) {
                        queue[r ++] = a.right;
                    }
                }
                ans.add(list);
            }
            return ans;
        }

        // 按层级map处理，看看就好
        // 提交时把方法名改为levelOrder，此方法为普通bfs，此题不推荐
        public static List<List<Integer>> levelOrder1(TreeNode root) {
            List<List<Integer>> ans = new ArrayList<>();
            if (root != null) {
                Queue<TreeNode> queue = new LinkedList<>();
                HashMap<TreeNode, Integer> levels = new HashMap<>();
                queue.add(root);
                levels.put(root, 0);
                while (!queue.isEmpty()) {
                    TreeNode cur = queue.poll();
                    int level = levels.get(cur);
                    if (ans.size() == level) {
                        ans.add(new ArrayList<>());
                    }
                    ans.get(level).add(cur.val);
                    if (cur.left != null) {
                        queue.add(cur.left);
                        levels.put(cur.left, level + 1);
                    }
                    if (cur.right != null) {
                        queue.add(cur.right);
                        levels.put(cur.right, level + 1);
                    }
                }
            }
            return ans;
        }
    }
}
